package 剑指offer.贪心与动态规划;

/**
 * 把一根绳子切成几段，求每段的长度之积的最大值
 * 有很多切法，所以要找最大值
 * <p>
 * 分析问题：这是一个求最优解的问题（最大值、最小值），应该想到 DP 或者贪心
 * 把绳子切分之后可能还会继续切分下去，所以又产生了子问题，解法一定是 DP 或者 贪心
 */
public class 第14题剪绳子 {

    /*
    动态规划和贪心：
    当一个问题涉及到最优解的时候、
    当问题可以分解成更小的问题的时候、（小问题还可能重叠）
    通过解决小问题从而解决最终问题

    自上而下分析
    自下而上求解

    动态规划无法一次性找到最优解，他需要遍历整个数据反复尝试

    贪心策略：
    使用的前提和 DP 一样 =>
        当一个问题涉及到最优解的时候、
        当问题可以分解成更小的问题的时候、（小问题还可能重叠）
        通过解决小问题从而解决最终问题

     不同的是贪心的每一步都是最优解，不需要反复尝试。
     要达到这个效果，需要通过数学分析找到突破点

     */

    /*
     动态规划求解：状态转移方程 f(n) = max{ f(i), f(n-i) }
     解释：
        一根绳子长度 n，第一刀剪下去，有 n-1 种剪法，剪出来的长度可能为 1,2,3...n-1
     那么，第 i 刀的时候就有 n - i 种剪法
      */
    public static int cutRope(int target) {
        if (target < 2)
            return 0;
        if (target == 2)
            return 1;
        if (target == 3)
            return 2;
        // 1. 先将子问题最优解暂存
        int[] tmp = new int[target + 1];
        tmp[0] = 0;
        tmp[1] = 1;
        tmp[2] = 2;
        tmp[3] = 3;
        // 2. 遍历剩余的全部数据，在子问题的最优解上得到最终问题的最优解
        int max = 0;
        for (int i = 4; i <= target; i++) { // i 代表target正在增加至待计算的值
            max = 0;
            for (int j = 1; j <= i / 2; j++) { // j 表示从子问题开始求解，注意边界是 i/2（减少重复计算）
                int product = tmp[j] * tmp[i - j];
                if (max < product) {
                    max = product;
                    tmp[i] = max;
                }

            }
        }
        return tmp[target];
    }


    // 贪心求解
    public static int cutRope2(int target) {
        if (target < 2)
            return 0;
        if (target == 2)
            return 1;
        if (target == 3)
            return 2;
        // 通过证明，每次切出 3 个长度是最优解
        // 但是最后一部分可能不够 3 个长度，可以切成 2 个长度
        int timesOf3 = target / 3;
        if (target - timesOf3 * 3 == 1) {
            timesOf3 -= 1;
        }
        int timesOf2 = (target - timesOf3 * 3) / 2;
        return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2));
    }

    public static void main(String[] args) {
        System.out.println(cutRope(4));
    }
}
